A hardware decompression engine that supports many concurrent compressed data streams may require a cache. A decompression cache may hold multiple segments of active data streams which require history based decompression. At the same time, a decompression cache is of finite size and cannot always hold the entire history for all active data streams. In practice, an active data stream can be quite large and instead of storing multiple data stream histories in their entirety on a cache, a portion of the most recent data for each data stream is stored.
In addition to controlling the amount of data stored in the cache for each data stream, a cache replacement policy may also be utilized to maximize the usage of space in the cache. For instance, a cache replacement policy may determine which data in the cache are to be replaced by newly incoming data. Known cache replacement policies include: Least Recently Used (LRU), Least Frequently Used (LFU), Random, LRU-2, 2Q, and Adaptive Replacement Cache (ARC). These cache replacement policies are all derived from the storage or processor (instruction/data) domains and are based on system addresses. However, these existing cache replacement policies are insufficient in handling decompression caches.